package com.zyk.leetcode;

import java.util.ArrayList;

/**
 * @author zhangsan
 * @date 2021/4/9 15:44
 */
public class M0406 {

    // https://leetcode-cn.com/problems/successor-lcci/
    // 中序后继节点
    public static TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if(root == null) { return null; }
        ArrayList<TreeNode> list = new ArrayList<>();
        in(root, list);

        for (int i = 0; i < list.size() - 1; i++) {
            if(list.get(i) == p) {
                return list.get(i+1);
            }
        }
        return null;
    }

    private static void in(TreeNode head, ArrayList<TreeNode> list) {
        if(head == null) { return; }
        in(head.left, list);
        list.add(head);
        in(head.right, list);
    }

    // 二叉搜索树
    public static TreeNode inorderSuccessor2(TreeNode root, TreeNode p) {
        TreeNode pre = null;
        while(root.val!=p.val){
            //右边
            if(p.val > root.val){
                root = root.right;
            }
            //左边
            else{
                pre = root;
                root = root.left;
            }
        }
        //假如没有右子树
        if(root.right==null){
            return pre;
        }
        else{
            root = root.right;
            while(root.left!=null){
                root = root.left;
            }
            return root;
        }
    }

    // for test
    public static void main(String[] args) {

    }

}
